Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/t3_1/doc.lha/documentation/manual/tree.mss

Text File | 1987-06-30 | 8KB | 224 lines

@part[TREE, root "TMAN.MSS"]    @Comment{-*-System:TMAN-*-}
@chap[Trees]
@label[TreesChapter]


@dc{ Bletch.  Rewrite this intro.  It's all out of order. }

This chapter describes procedures available for manipulating trees.  The
term @iixs[tree] is used in a technical sense to refer to non-circular
list structure considered as tree data-structures, as contrasted with
@i[lists], which use chained pairs to represent a one-dimensional
sequence of objects.  Thus one might say either that @wt[(A (B C) D)] is
a list of three elements, or that it is a tree with four (non-null)
leaves.

Trees are used to represent programs.  The tree-manipulation
procedures and special forms are designed with this in mind.
@dc{ The tree paradigm may be useful for other things also. }


@section[Comparison]
@index[Equality predicates]

@desc[(EQUIV? @i[object1 object2]) @yl[] @i[boolean]]
@tc[EQUIV?] is an equality predicate, not for comparing trees but for
comparing leaves.

@itemize[
If @tc[(EQ? @i[object1] @i[object2])], then
@tc[(EQUIV? @i[object1] @i[object2])].

If @i[object1] and @i[object2] are both numbers of the same type,
then they are @tc[EQUIV?] iff they have the same numeric value
(see @tc[=], page @pageref[EQUAL?]).

If @i[object1] and @i[object2] are both strings,
then they are @tc[EQUIV?] if they are @tc[STRING-EQUAL?]
(page @pageref[STRING-EQUAL?]).
]
See also the descriptions of @tc[EQ?] (page @pageref[EQ?]) and @tc[=]
(page @pageref[EQUAL?]).

    @BeginInset[Bug:]
    In @Timp[] 2.7, @tc[EQUIV?] (and @tc[ALIKEV?]) may return false
    for two numbers which are @tc[=].  It will do the right thing,
    however, for integers which are less than 2@+[28] in magnitude.
    @EndInset[]
@EndDesc[EQUIV?]

@dc{ There ought to be an entire section on equality, describing the
relative merits and disadvantages of @tc[EQ?], @tc[EQUAL?], @tc[EQUIV?],
@tc[ALIKEQ?], and @tc[ALIKEV?]. }

@desc[@el[](ALIKE? @i[predicate tree1 tree2]) @yl[] @i[boolean]]
Returns true if @i[tree1] and @i[tree2] have the same shape
and their corresponding leaves are equal according to
@i[predicate], which must be an equality predicate.
@begin[ProgramExample]
(ALIKE? = '(1 (2 . 8) 3) '(1 (2 . 8) 3))  @ev[]  @r[true]
@end[ProgramExample]
@EndDesc[ALIKE?]

@desc[(ALIKEQ? @i[tree1 tree2]) @yl[] @i[boolean]]
  @begin[ProgramExample]
(ALIKEQ? @i[tree1 tree2])  @ce[]  (ALIKE? EQ? @i[tree1 tree2])
  @end[ProgramExample]
@EndDesc[ALIKEQ?]

@info[EQUIV="EQUAL"]
@desc[@el[](ALIKEV? @i[tree1 tree2]) @yl[] @i[boolean]]
@ProgramExample[
(ALIKEV? @i[tree1] @i[tree2])  @ce[]  (ALIKE? EQUIV? @i[tree1] @i[tree2])
]
@label[ALIKEV]
Roughly speaking, two trees are @tc[ALIKEV?] if they print the
same way.
@EndDesc[ALIKEV?]


@section[Tree utilities]

@desc[(SUBST @i[predicate new old tree]) @yl[] @i[tree]]
Returns a result tree which is the same as the argument @i[tree],
except that leaves in the argument tree which, according to
@i[predicate], are equal to @i[old], have been changed to be
@i[new].  @i[Predicate] must be an equality predicate.
  @begin[ProgramExample]
(SUBST EQUIV? 17 13 '(10 (20 13) 30))  @ev[]  (10 (20 17) 30)
  @end[ProgramExample]
The result returned by @tc[SUBST] may or may not share structure with its
tree argument.
@EndDesc[SUBST]

@desc[(SUBSTQ @i[new old tree]) @yl[] @i[tree]]
@ProgramExample[(SUBSTQ @i[new old tree])  @ce[]  (SUBST EQ? @i[new old tree])]
@EndDesc[SUBSTQ]

@info[EQUIV="SUBST"]
@desc[(SUBSTV @i[new old tree]) @yl[] @i[tree]]
@begin[ProgramExample]
(SUBSTV @i[new old tree])  @ce[]  (SUBST EQUIV? @I[new old tree])
@end[ProgramExample]
@EndDesc[SUBSTV]

@desc[(COPY-TREE @i[tree]) @yl[] @i[tree]]
Recursively make a copy of the @i[tree].
@ProgramExample[(COPY-TREE @i[tree])  @ce[]  (SUBSTQ NIL NIL @i[tree])]
@EndDesc[COPY-TREE]

@desc[(TREE-HASH @i[tree]) @yl[] @i[integer]]
Compute a @ix[hash code] for @i[tree].
The hash computed is a non-negative fixnum with the property
that if @i[tree1] and @i[tree2] are @tc[ALIKEV?],
then their hashes are the same.
@dc{ Same across all @Tau[] implementations, or not? }
@EndDesc[TREE-HASH]


@section[Destructuring]

@info[Notes="Special form"]
@desc[(DESTRUCTURE @i[specs . body]) @yl[] @i[value-of-body]]
@i[Specs] has the form @wt[((@i[pattern value]) (@i[pattern value]) ...)]
where each @i[pattern] is either an identifier (e.g., @tc[X])
or a @i[tree] (see page @PageRef[TreesChapter]),
all of whose non-null leaves are identifiers
(e.g., @wt[((X Y . Z) P Q)]).

@tc[DESTRUCTURE] is similar to @tc[LET], and in the case that all the
@i[patterns] are symbols, @tc[DESTRUCTURE] and @tc[LET] are
equivalent. But @tc[DESTRUCTURE] is especially useful when one wants
to bind variables to the various nodes in a single tree structure.  For
example, suppose @tc[Z] has the value @wt[(1 (2 3) ((4 5 . 6) 7))],
and we want to bind @tc[A @r[to] 1, B @r[to] 2, C @r[to] (3),
D @r[to] 6, @r[and] E @r[to] 7]. We could write
@begin[ProgramExample]
(LET ((A (CAR Z))
      (B (CAADR Z))
      (C (CDADR Z))
      (D (CDDAR (CADDR Z)))
      (E (CADADR (CDR Z))))
  ...)
@end[ProgramExample]
However, we could also write
@begin[ProgramExample]
(DESTRUCTURE (((A (B . C) ((() () . D) E)) Z))
  ...)
@end[ProgramExample]
The @tc[()]'s notate ignored positions.
@EndDesc[DESTRUCTURE]

@info[Notes="Special form"]
@desc[(DESTRUCTURE* @i[specs . body]) @yl[] @i[value-of-body]]
@tc[DESTRUCTURE*] is the @qu"serial" form of @tc[DESTRUCTURE], just
as @tc[LET*] is the @qu"serial" form of @tc[LET].
@begin[ProgramExample]
(DESTRUCTURE* ((@i[pattern@-(1) value@-(1)])
               (@i[pattern@-(2) value@-(2)])
               ...
               (@i[pattern@-(n) value@-(n)]))
  @i[code])
  @ce[]
(DESTRUCTURE ((@i[pattern@-(1) value@-(1)]))
  (DESTRUCTURE ((@i[pattern@-(1) value@-(1)]))
   ...
     (DESTRUCTURE ((@i[pattern@-(n) value@-(n)]))
       @i[code] )...))
@end[ProgramExample]
@EndDesc[DESTRUCTURE*]


@section[Backquote]
@Label[backquote section]    @Comment{ref: syntax chapter}
@index[Backquote]@index[Quasi-quote]

@tau[]'s @i[backquote] facility, inherited from the Maclisp family
of Lisps, is useful for building programs whose form
is determined, but where some of the structure is constant
and some is to be filled in.
This is especially convenient in the definitions of macro
expanders.
It is so useful that a special external syntax is provided
for notating such templates.
It takes its name from the name
of the character (backquote, @tc[`]) which introduces this special syntax.

The functionality provided by backquote is sometimes called @qu(quasi-quote)
because it behaves like @tc[QUOTE] except that one can specify that
subforms of the backquoted form should be evaluated.  Inside a form
that is preceded by a backquote, two additional pieces of
external syntax are active: comma (@tc[,]), and comma at-sign (@tc[,@@]);
these are the ways to indicate that some subform should
be evaluated (i.e., unquoted).  A subform preceded by a comma
is evaluated and replaced by the result of the evaluation.
A subform preceded by a comma at-sign is evaluated and replaced
by @i[splicing in] the result of the evaluation.

Here are some simple examples.  Note that the first example shows code
equivalence, not evaluation.
@begin[ProgramExample]
`(A B ,X Y)  @ce[]  (LIST 'A 'B X 'Y)

(DEFINE X '(3))
(CDR `(A B ,X C))    @ev[]  (B (3) C)
(CDR `(A B ,@@X C))  @ev[]  (B 3 C)

(DEFINE-SYNTAX (REPEAT N . CODE)     ;Execute CODE N times
  `(LET ((COUNT ,N) (THUNK (LAMBDA () ,@@CODE)))
     (DO ((COUNT COUNT (-1+ COUNT)))
         ((<=0? COUNT) '())
       (THUNK))))
@end[ProgramExample]

It is possible to nest backquoted forms.  This is useful when writing complex
source-to-source transformations.
  @begin[ProgramExample]
(DEFINE-SYNTAX (FOO X Y)
  `(LET ((STUFF ,X))
     `((STUFF-IS ,STUFF)
       (Y-IS ,',Y))))

(FOO (+ 3 5) BAZ)  @ev[]  ((STUFF-IS 8) (Y-IS BAZ))
  @end[ProgramExample]